// // #include <iostream>
// // #include <cstring>
// // using namespace std;


// // const int N = 210;
// // int g[N][N] , dis[N];
// // int n , m;
// // bool st[N];
// // void dijkstra()
// // {
// //     memset(dis,0x3f,sizeof dis);
// //     dis[1] = 0;
// //     for(int i = 0 ; i < n ; ++i)
// //     {
// //         int t = -1;
// //         for(int j = 1 ; j <= n ; ++j)
// //             if(!st[j] && (t == -1 || dis[j] < dis[t])) t = j;

// //         st[t] = true;
// //         for(int j = 1 ; j <= n ; ++j)
// //             dis[j] = min(dis[j],dis[t] + g[t][j]);
// //     }
// // }

// // int main()
// // {
// //     while(true)
// //     {
// //         scanf("%d%d",&n,&m);
// //         memset(g,0x3f,sizeof g);
// //         memset(st,0,sizeof st);
// //         if(n == 0 && m == 0) break;
// //         for(int i = 0 ; i < m ; ++i){
// //             int a , b , w;
// //             scanf("%d%d%d",&a,&b,&w);
// //             g[a][b] = g[b][a] = w;
// //         }
// //         dijkstra();
// //         printf("%d\n",dis[n]);
// //     }
// //     return 0;
// // }



// // #include <iostream>
// // #include <cstring>
// // using namespace std;
// // const int N = 210;
// // int g[N][N];
// // int dis[N];
// // bool st[N];
// // int n , m;

// // int dijkstra()
// // {
// //     memset(dis,0x3f,sizeof dis);
// //     dis[1] = 0;
// //     for(int i = 0 ; i < n ; ++i)
// //     {
// //         int t = -1;
// //         for(int j = 1 ; j <= n ; ++j)
// //             if(!st[j] && (t == -1 || dis[t] > dis[j])) t = j;

// //         st[t] = true;
// //         for(int j = 1 ; j <= n ; ++j)
// //             dis[j] = min(dis[j],dis[t] + g[t][j]);
// //     }
// //     return dis[n];
// // }


// // int main()
// // {
// //     while(true)
// //     {
// //         scanf("%d%d",&n,&m);
// //         memset(g,0x3f,sizeof g);
// //         memset(st,0,sizeof st);
// //         if(n == 0 && m == 0) break;
// //         for(int i = 0 ; i < m ; ++i)
// //         {
// //             int a , b , w;
// //             cin >> a >> b >> w;
// //             g[a][b] = g[b][a] = w;
// //         }
// //         int t = dijkstra();
// //         printf("%d\n",t);
// //     }
// //     return 0;
// // }



// #include <iostream>
// #include <cstring>
// #include <queue>
// using namespace std;

// const int N = 1e5 + 10 , M = 5e6 + 10;
// int n , m , s;
// int dis[N] , h[N] , w[N] , e[M] , ne[M] , idx;
// using PII = pair<int,int>;
// priority_queue<PII> pq;
// void add(int a , int b , int c)
// {
//     e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
// }

// void dijkstra(int s)
// {
//     memset(dis,0x3f,sizeof dis);
//     dis[s] = 0;
//     pq.push({0,s});
//     while(!pq.empty())
//     {
//         auto t = pq.top();
//         pq.pop();
//         auto ver = t.second , distance = t.first;
//         if(st[ver]) continue;
//         st[ver] = true;
//         for(int i = h[ver] ; i != -1 ; i = ne[i])
//         {
//             int j = e[i];
//             if(!st[j])
//             {
//                 dis[j] = min(dis[j],distance + w[i]);
//                 pq.push({dis[j],j});
//             }
//         }
//     }
// }

// int main()
// {
//     cin >> n >> m >> s;
//     memset(h,-1,sizeof(h));
//     for(int i = 0 ; i < m ; ++i)
//     {
//         int a , b , w;
//         scanf("%d%d%d",&a,&b,&w);
//         add(a,b,w);
//     }
//     dijkstra(s);
//     for(int i = 1 ; i <= n ; ++i) printf("%d ",dis[i]);
//     return 0;
// }

// #include <iostream>
// #include <queue>
// #include <cstring>
// using namespace std;
// const int N = 1010 , M = 10010;
// int dis[N] , h[N] , w[M] , ne[M] , e[M] , idx;
// bool st[N];
// queue<int> q;
// int n , m , s;

// void add(int a , int b , int c)
// {
//     e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
// }

// void spfa()
// {
//     memset(dis,0x3f,sizeof dis);
//     q.push(s);
//     st[s] = true;
//     while(!q.empty())
//     {
//         auto t = q.front();
//         q.pop();
//         st[t] = false;
//         for(int i = h[t] ; i != -1 ; i = ne[i])
//         {
//             int j = e[i];
//             if(dis[j] > dis[t] + w[i])
//             {
//                 dis[j] = dis[t] + w[i];
//                 if(!st[j])
//                 {
//                     q.push(j);
//                     st[j] = true;
//                 }
//             }
//         }
//     }
// }

// int main()
// {
//     cin >> n >> m >> s;
//     memset(h,-1,sizeof h);
//     for(int i = 0 ; i < m ; ++i)
//     {
//         int a , b , c;
//         cin >> a >> b >> c;
//         add(a,b,c);
//     }
//     spfa();
//     for(int i = 1 ; i <= n ; ++i)
//         if(dis[i] > 0x3f3f3f3f / 2) printf("%d ",0x7fffffff);
//         else printf("%d ",dis[i]);
//     return 0;
// }

